Graph< captype, tcaptype, flowtype > Class Template Reference

Current instantiations are in instances.inc. More...

#include <graph.h>

List of all members.

Public Types

typedef int node_id
 terminals
typedef arcarc_id
 SOURCE = 0
 SINK = 1
enum  termtype { SOURCE = 0, SINK = 1 }

Public Member Functions

 Graph (int node_num_max, int edge_num_max, void(*err_function)(char *)=NULL)
 (should be enough for most applications)
 ~Graph ()
 Destructor.
node_id add_node (int num=1)
void add_edge (node_id i, node_id j, captype cap, captype rev_cap)
void add_tweights (node_id i, tcaptype cap_source, tcaptype cap_sink)
flowtype maxflow (bool reuse_trees=false, Block< node_id > *changed_list=NULL)
termtype what_segment (node_id i, termtype default_segm=SOURCE)
void reset ()
arc_id get_first_arc ()
arc_id get_next_arc (arc_id a)
int get_node_num ()
 other functions for reading graph structure
int get_arc_num ()
void get_arc_ends (arc_id a, node_id &i, node_id &j)
tcaptype get_trcap (node_id i)
 returns residual capacity of SOURCE->i minus residual capacity of i->SINK
captype get_rcap (arc *a)
 returns residual capacity of arc a
void set_trcap (node_id i, tcaptype trcap)
void set_rcap (arc *a, captype rcap)
void mark_node (node_id i)
void remove_from_changed_list (node_id i)
void start_save ()
void stop_save ()
void restore_arc (arc *dest, const arc &s)
void restore_node (node *dest, const node &s)
void restore_saved ()
void save_node (node *x)
void save_arc (arc *x)
void save (node *x)
void save (node &x)
void save (arc *x)
void save (arc &x)

Public Attributes

graph_save save

Private Member Functions

void reallocate_nodes (int num)
 monotonically increasing global counter
void reallocate_arcs ()
 num is the number of new nodes
void set_active (node *i)
 functions for processing active list
nodenext_active ()
void set_orphan_front (node *i)
 functions for processing orphans list
void set_orphan_rear (node *i)
 add to the beginning of the list
void add_to_changed_list (node *i)
 add to the end of the list
void maxflow_init ()
void maxflow_reuse_trees_init ()
 called if reuse_trees == false
void augment (arc *middle_arc)
 called if reuse_trees == true
void process_source_orphan (node *i)
void process_sink_orphan (node *i)
void test_consistency (node *current_node=NULL)

Private Attributes

nodenodes
nodenode_last
nodenode_max
 node_last = nodes+node_num, node_max = nodes+node_num_max;
arcarcs
arcarc_last
arcarc_max
 arc_last = arcs+2*edge_num, arc_max = arcs+2*edge_num_max;
int node_num
DBlock< nodeptr > * nodeptr_block
void(* error_function )(char *)
flowtype flow
int maxflow_iteration
 reusing trees & list of changed pixels
Block< node_id > * changed_list
 counter
nodequeue_first [2]
nodequeue_last [2]
nodeptrorphan_first
 list of active nodes
nodeptrorphan_last
int TIME
 list of pointers to orphans

Static Private Attributes

static const int NODEPTR_BLOCK_SIZE = 128

Classes

struct  arc
class  graph_save
 debug function More...
struct  node
 internal variables and functions More...
struct  nodeptr


Detailed Description

template<typename captype, typename tcaptype, typename flowtype>
class Graph< captype, tcaptype, flowtype >

Current instantiations are in instances.inc.

captype: type of edge capacities (excluding t-links) tcaptype: type of t-links (edges between nodes and terminals) flowtype: type of total flow

Definition at line 57 of file graph.h.


Member Typedef Documentation

template<typename captype, typename tcaptype, typename flowtype>
typedef arc* Graph< captype, tcaptype, flowtype >::arc_id

The following two functions return arcs in the same order that they were added to the graph. NOTE: for each call add_edge(i,j,cap,cap_rev) the first arc returned will be i->j, and the second j->i. If there are no more arcs, then the function can still be called, but the returned arc_id is undetermined.

Definition at line 158 of file graph.h.

template<typename captype, typename tcaptype, typename flowtype>
typedef int Graph< captype, tcaptype, flowtype >::node_id

terminals

Definition at line 65 of file graph.h.


Member Enumeration Documentation

template<typename captype, typename tcaptype, typename flowtype>
enum Graph::termtype

Enumerator:
SOURCE 
SINK 

Definition at line 60 of file graph.h.

00061         {
00062                 SOURCE  = 0,
00063                 SINK    = 1
00064         } termtype; 


Constructor & Destructor Documentation

template<typename captype, typename tcaptype, typename flowtype>
Graph< captype, tcaptype, flowtype >::Graph ( int  node_num_max,
int  edge_num_max,
void(*)(char *)  err_function = NULL 
)

(should be enough for most applications)

Constructor. The first argument gives an estimate of the maximum number of nodes that can be added to the graph, and the second argument is an estimate of the maximum number of edges. The last (optional) argument is the pointer to the function which will be called if an error occurs; an error message is passed to this function. If this argument is omitted, exit(1) will be called.

IMPORTANT: It is possible to add more nodes to the graph than node_num_max (and node_num_max can be zero). However, if the count is exceeded, then the internal memory is reallocated (increased by 50%) which is expensive. Also, temporarily the amount of allocated memory would be more than twice than needed. Similarly for edges. If you wish to avoid this overhead, you can download version 2.2, where nodes and edges are stored in blocks.

Definition at line 12 of file graph.cpp.

00013         : node_num(0),
00014           nodeptr_block(NULL),
00015           error_function(err_function)
00016 {
00017         if (node_num_max < 16) node_num_max = 16;
00018         if (edge_num_max < 16) edge_num_max = 16;
00019 
00020         nodes = (node*) malloc(node_num_max*sizeof(node));
00021         arcs = (arc*) malloc(2*edge_num_max*sizeof(arc));
00022         if (!nodes || !arcs) { if (error_function) (*error_function)("Not enough memory!"); exit(1); }
00023 
00024         node_last = nodes;
00025         node_max = nodes + node_num_max;
00026         arc_last = arcs;
00027         arc_max = arcs + 2*edge_num_max;
00028 
00029         maxflow_iteration = 0;
00030         flow = 0;
00031 }

template<typename captype, typename tcaptype, typename flowtype>
Graph< captype, tcaptype, flowtype >::~Graph (  ) 

Destructor.

Definition at line 34 of file graph.cpp.

00035 {
00036         if (nodeptr_block) 
00037         { 
00038                 delete nodeptr_block; 
00039                 nodeptr_block = NULL; 
00040         }
00041         free(nodes);
00042         free(arcs);
00043 }


Member Function Documentation

template<typename captype, typename tcaptype, typename flowtype>
void Graph< captype, tcaptype, flowtype >::add_edge ( node_id  i,
node_id  j,
captype  cap,
captype  rev_cap 
) [inline]

Adds a bidirectional edge between 'i' and 'j' with the weights 'cap' and 'rev_cap'. IMPORTANT: see note about the constructor

Definition at line 517 of file graph.h.

00518 {
00519         assert(_i >= 0 && _i < node_num);
00520         assert(_j >= 0 && _j < node_num);
00521         assert(_i != _j);
00522         assert(cap >= 0);
00523         assert(rev_cap >= 0);
00524 
00525         if (arc_last == arc_max) reallocate_arcs();
00526 
00527         arc *a = arc_last ++;
00528         arc *a_rev = arc_last ++;
00529 
00530         node* i = nodes + _i;
00531         node* j = nodes + _j;
00532         
00533         a -> sister = a_rev;
00534         a_rev -> sister = a;
00535         a -> next = i -> first;
00536         i -> first = a;
00537         a_rev -> next = j -> first;
00538         j -> first = a_rev;
00539         a -> head = j;
00540         a_rev -> head = i;
00541         a -> r_cap = cap;
00542         a_rev -> r_cap = rev_cap;
00543 }

template<typename captype, typename tcaptype, typename flowtype>
Graph< captype, tcaptype, flowtype >::node_id Graph< captype, tcaptype, flowtype >::add_node ( int  num = 1  )  [inline]

Adds node(s) to the graph. By default, one node is added (num=1); then first call returns 0, second call returns 1, and so on. If num>1, then several nodes are added, and node_id of the first one is returned. IMPORTANT: see note about the constructor

Definition at line 476 of file graph.h.

00477 {
00478         assert(num > 0);
00479 
00480         if (node_last + num > node_max) reallocate_nodes(num);
00481 
00482         if (num == 1)
00483         {
00484                 node_last -> first = NULL;
00485                 node_last -> tr_cap = 0;
00486                 node_last -> is_marked = 0;
00487                 node_last -> is_in_changed_list = 0;
00488 
00489                 node_last ++;
00490                 return node_num++;
00491         }
00492         else
00493         {
00494                 memset(node_last, 0, num*sizeof(node));
00495 
00496                 node_id i = node_num;
00497                 node_num += num;
00498                 node_last += num;
00499                 return i;
00500         }
00501 }

template<typename captype, typename tcaptype, typename flowtype>
void Graph< captype, tcaptype, flowtype >::add_to_changed_list ( node i  )  [inline, private]

add to the end of the list

Definition at line 107 of file maxflow.cpp.

00108 {
00109         if (changed_list && !i->is_in_changed_list)
00110         {
00111                 node_id* ptr = changed_list->New();
00112                 *ptr = (node_id)(i - nodes);
00113                 i->is_in_changed_list = true;
00114         }
00115 }

template<typename captype, typename tcaptype, typename flowtype>
void Graph< captype, tcaptype, flowtype >::add_tweights ( node_id  i,
tcaptype  cap_source,
tcaptype  cap_sink 
) [inline]

Adds new edges 'SOURCE->i' and 'i->SINK' with corresponding weights. Can be called multiple times for each node. Weights can be negative. NOTE: the number of such edges is not counted in edge_num_max. No internal memory is allocated by this call.

Definition at line 504 of file graph.h.

00505 {
00506         assert(i >= 0 && i < node_num);
00507 
00508         tcaptype delta = nodes[i].tr_cap;
00509         if (delta > 0) cap_source += delta;
00510         else           cap_sink   -= delta;
00511         flow += (cap_source < cap_sink) ? cap_source : cap_sink;
00512         save(nodes[i]);
00513         nodes[i].tr_cap = cap_source - cap_sink;
00514 }

template<typename captype, typename tcaptype, typename flowtype>
void Graph< captype, tcaptype, flowtype >::augment ( arc middle_arc  )  [private]

called if reuse_trees == true

Definition at line 245 of file maxflow.cpp.

00246 {
00247         node *i;
00248         arc *a;
00249         tcaptype bottleneck;
00250 
00251 
00252         /* 1. Finding bottleneck capacity */
00253         /* 1a - the source tree */
00254         bottleneck = middle_arc -> r_cap;
00255         for (i=middle_arc->sister->head; ; i=a->head)
00256         {
00257                 a = i -> parent;
00258                 if (a == TERMINAL) break;
00259                 if (bottleneck > a->sister->r_cap) bottleneck = a -> sister -> r_cap;
00260         }
00261         if (bottleneck > i->tr_cap) bottleneck = i -> tr_cap;
00262         /* 1b - the sink tree */
00263         for (i=middle_arc->head; ; i=a->head)
00264         {
00265                 a = i -> parent;
00266                 if (a == TERMINAL) break;
00267                 if (bottleneck > a->r_cap) bottleneck = a -> r_cap;
00268         }
00269         if (bottleneck > - i->tr_cap) bottleneck = - i -> tr_cap;
00270 
00271 
00272         /* 2. Augmenting */
00273         /* 2a - the source tree */
00274         save(middle_arc -> sister);
00275         middle_arc -> sister -> r_cap += bottleneck;
00276         save(middle_arc);
00277         middle_arc -> r_cap -= bottleneck;
00278         for (i=middle_arc->sister->head; ; i=a->head)
00279         {
00280                 a = i -> parent;
00281                 if (a == TERMINAL) break;
00282                 save(a);
00283                 a -> r_cap += bottleneck;
00284                 save(a -> sister);
00285                 a -> sister -> r_cap -= bottleneck;
00286                 if (!a->sister->r_cap)
00287                 {
00288                         set_orphan_front(i); // add i to the beginning of the adoption list
00289                 }
00290         }
00291         save(i);
00292         i -> tr_cap -= bottleneck;
00293         if (!i->tr_cap)
00294         {
00295                 set_orphan_front(i); // add i to the beginning of the adoption list
00296         }
00297         /* 2b - the sink tree */
00298         for (i=middle_arc->head; ; i=a->head)
00299         {
00300                 a = i -> parent;
00301                 if (a == TERMINAL) break;
00302                 save(a->sister);
00303                 a -> sister -> r_cap += bottleneck;
00304                 save(a);
00305                 a -> r_cap -= bottleneck;
00306                 if (!a->r_cap)
00307                 {
00308                         set_orphan_front(i); // add i to the beginning of the adoption list
00309                 }
00310         }
00311         save(i);
00312         i -> tr_cap += bottleneck;
00313         if (!i->tr_cap)
00314         {
00315                 set_orphan_front(i); // add i to the beginning of the adoption list
00316         }
00317 
00318         flow += bottleneck;
00319 }

template<typename captype, typename tcaptype, typename flowtype>
void Graph< captype, tcaptype, flowtype >::get_arc_ends ( arc_id  a,
node_id i,
node_id j 
)

template<typename captype, typename tcaptype, typename flowtype>
int Graph< captype, tcaptype, flowtype >::get_arc_num (  )  [inline]

Definition at line 164 of file graph.h.

00164 { return (int)(arc_last - arcs); }

template<typename captype, typename tcaptype, typename flowtype>
Graph< captype, tcaptype, flowtype >::arc * Graph< captype, tcaptype, flowtype >::get_first_arc (  )  [inline]

Definition at line 546 of file graph.h.

00547 {
00548         return arcs;
00549 }

template<typename captype, typename tcaptype, typename flowtype>
arc_id Graph< captype, tcaptype, flowtype >::get_next_arc ( arc_id  a  ) 

template<typename captype, typename tcaptype, typename flowtype>
int Graph< captype, tcaptype, flowtype >::get_node_num (  )  [inline]

other functions for reading graph structure

Definition at line 163 of file graph.h.

00163 { return node_num; }

template<typename captype, typename tcaptype, typename flowtype>
captype Graph< captype, tcaptype, flowtype >::get_rcap ( arc a  )  [inline]

returns residual capacity of arc a

Definition at line 573 of file graph.h.

00574 {
00575         assert(a >= arcs && a < arc_last);
00576         return a->r_cap;
00577 }

template<typename captype, typename tcaptype, typename flowtype>
tcaptype Graph< captype, tcaptype, flowtype >::get_trcap ( node_id  i  )  [inline]

returns residual capacity of SOURCE->i minus residual capacity of i->SINK

3. Functions for reading residual capacities. //

Definition at line 566 of file graph.h.

00567 {
00568         assert(i>=0 && i<node_num);
00569         return nodes[i].tr_cap;
00570 }

template<typename captype, typename tcaptype, typename flowtype>
void Graph< captype, tcaptype, flowtype >::mark_node ( node_id  i  )  [inline]

If flag reuse_trees is true while calling maxflow(), then search trees are reused from previous maxflow computation. In this case before calling maxflow() the user must specify which parts of the graph have changed by calling mark_node(): add_tweights(i),set_trcap(i) => call mark_node(i) add_edge(i,j),set_rcap(a) => call mark_node(i); mark_node(j)

This option makes sense only if a small part of the graph is changed. The initialization procedure goes only through marked nodes then.

mark_node(i) can either be called before or after graph modification. Can be called more than once per node, but calls after the first one do not have any effect.

NOTE:

Definition at line 609 of file graph.h.

00610 {
00611         node* i = nodes + _i;
00612         if (!i->next)
00613         {
00614                 /* it's not in the list yet */
00615                 if (queue_last[1]) queue_last[1] -> next = i;
00616                 else               queue_first[1]        = i;
00617                 queue_last[1] = i;
00618                 i -> next = i;
00619         }
00620         i->is_marked = 1;
00621 }

template<typename captype, typename tcaptype, typename flowtype>
flowtype Graph< captype, tcaptype, flowtype >::maxflow ( bool  reuse_trees = false,
Block< node_id > *  changed_list = NULL 
)

Computes the maxflow. Can be called several times. FOR DESCRIPTION OF reuse_trees, SEE mark_node(). FOR DESCRIPTION OF changed_list, SEE remove_from_changed_list().

Definition at line 480 of file maxflow.cpp.

00481 {
00482         node *i, *j, *current_node = NULL;
00483         arc *a;
00484         nodeptr *np, *np_next;
00485 
00486         if (!nodeptr_block)
00487         {
00488                 nodeptr_block = new DBlock<nodeptr>(NODEPTR_BLOCK_SIZE, error_function);
00489         }
00490 
00491         changed_list = _changed_list;
00492         if (maxflow_iteration == 0 && reuse_trees) { if (error_function) (*error_function)("reuse_trees cannot be used in the first call to maxflow()!"); exit(1); }
00493         if (changed_list && !reuse_trees) { if (error_function) (*error_function)("changed_list cannot be used without reuse_trees!"); exit(1); }
00494 
00495         if (reuse_trees) maxflow_reuse_trees_init();
00496         else             maxflow_init();
00497 
00498         // main loop
00499         while ( 1 )
00500         {
00501                 // test_consistency(current_node);
00502 
00503                 if ((i=current_node))
00504                 {
00505                         i -> next = NULL; /* remove active flag */
00506                         if (!i->parent) i = NULL;
00507                 }
00508                 if (!i)
00509                 {
00510                         if (!(i = next_active())) break;
00511                 }
00512 
00513                 /* growth */
00514                 if (!i->is_sink)
00515                 {
00516                         /* grow source tree */
00517                         for (a=i->first; a; a=a->next)
00518                         if (a->r_cap)
00519                         {
00520                                 j = a -> head;
00521                                 if (!j->parent)
00522                                 {
00523                                         j -> is_sink = 0;
00524                                         j -> parent = a -> sister;
00525                                         j -> TS = i -> TS;
00526                                         j -> DIST = i -> DIST + 1;
00527                                         set_active(j);
00528                                         add_to_changed_list(j);
00529                                 }
00530                                 else if (j->is_sink) break;
00531                                 else if (j->TS <= i->TS &&
00532                                          j->DIST > i->DIST)
00533                                 {
00534                                         /* heuristic - trying to make the distance from j to the source shorter */
00535                                         j -> parent = a -> sister;
00536                                         j -> TS = i -> TS;
00537                                         j -> DIST = i -> DIST + 1;
00538                                 }
00539                         }
00540                 }
00541                 else
00542                 {
00543                         /* grow sink tree */
00544                         for (a=i->first; a; a=a->next)
00545                         if (a->sister->r_cap)
00546                         {
00547                                 j = a -> head;
00548                                 if (!j->parent)
00549                                 {
00550                                         j -> is_sink = 1;
00551                                         j -> parent = a -> sister;
00552                                         j -> TS = i -> TS;
00553                                         j -> DIST = i -> DIST + 1;
00554                                         set_active(j);
00555                                         add_to_changed_list(j);
00556                                 }
00557                                 else if (!j->is_sink) { a = a -> sister; break; }
00558                                 else if (j->TS <= i->TS &&
00559                                          j->DIST > i->DIST)
00560                                 {
00561                                         /* heuristic - trying to make the distance from j to the sink shorter */
00562                                         j -> parent = a -> sister;
00563                                         j -> TS = i -> TS;
00564                                         j -> DIST = i -> DIST + 1;
00565                                 }
00566                         }
00567                 }
00568 
00569                 TIME ++;
00570 
00571                 if (a)
00572                 {
00573                         i -> next = i; /* set active flag */
00574                         current_node = i;
00575 
00576                         /* augmentation */
00577                         augment(a);
00578                         /* augmentation end */
00579 
00580                         /* adoption */
00581                         while ((np=orphan_first))
00582                         {
00583                                 np_next = np -> next;
00584                                 np -> next = NULL;
00585 
00586                                 while ((np=orphan_first))
00587                                 {
00588                                         orphan_first = np -> next;
00589                                         i = np -> ptr;
00590                                         nodeptr_block -> Delete(np);
00591                                         if (!orphan_first) orphan_last = NULL;
00592                                         if (i->is_sink) process_sink_orphan(i);
00593                                         else            process_source_orphan(i);
00594                                 }
00595 
00596                                 orphan_first = np_next;
00597                         }
00598                         /* adoption end */
00599                 }
00600                 else current_node = NULL;
00601         }
00602         // test_consistency();
00603 
00604         if (!reuse_trees || (maxflow_iteration % 64) == 0)
00605         {
00606                 delete nodeptr_block; 
00607                 nodeptr_block = NULL; 
00608         }
00609 
00610         maxflow_iteration ++;
00611         return flow;
00612 }

template<typename captype, typename tcaptype, typename flowtype>
void Graph< captype, tcaptype, flowtype >::maxflow_init (  )  [private]

Definition at line 120 of file maxflow.cpp.

00121 {
00122         node *i;
00123 
00124         queue_first[0] = queue_last[0] = NULL;
00125         queue_first[1] = queue_last[1] = NULL;
00126         orphan_first = NULL;
00127 
00128         TIME = 0;
00129 
00130         for (i=nodes; i<node_last; i++)
00131         {
00132                 i -> next = NULL;
00133                 i -> is_marked = 0;
00134                 i -> is_in_changed_list = 0;
00135                 i -> TS = TIME;
00136                 if (i->tr_cap > 0)
00137                 {
00138                         /* i is connected to the source */
00139                         i -> is_sink = 0;
00140                         i -> parent = TERMINAL;
00141                         set_active(i);
00142                         i -> DIST = 1;
00143                 }
00144                 else if (i->tr_cap < 0)
00145                 {
00146                         /* i is connected to the sink */
00147                         i -> is_sink = 1;
00148                         i -> parent = TERMINAL;
00149                         set_active(i);
00150                         i -> DIST = 1;
00151                 }
00152                 else
00153                 {
00154                         i -> parent = NULL;
00155                 }
00156         }
00157 }

template<typename captype, typename tcaptype, typename flowtype>
void Graph< captype, tcaptype, flowtype >::maxflow_reuse_trees_init (  )  [private]

called if reuse_trees == false

Definition at line 160 of file maxflow.cpp.

00161 {
00162         node* i;
00163         node* j;
00164         node* queue = queue_first[1];
00165         arc* a;
00166         nodeptr* np;
00167 
00168         queue_first[0] = queue_last[0] = NULL;
00169         queue_first[1] = queue_last[1] = NULL;
00170         orphan_first = orphan_last = NULL;
00171 
00172         TIME ++;
00173 
00174         while ((i=queue))
00175         {
00176                 queue = i->next;
00177                 if (queue == i) queue = NULL;
00178                 i->next = NULL;
00179                 i->is_marked = 0;
00180                 set_active(i);
00181 
00182                 if (i->tr_cap == 0)
00183                 {
00184                         if (i->parent) set_orphan_rear(i);
00185                         continue;
00186                 }
00187 
00188                 if (i->tr_cap > 0)
00189                 {
00190                         if (!i->parent || i->is_sink)
00191                         {
00192                                 i->is_sink = 0;
00193                                 for (a=i->first; a; a=a->next)
00194                                 {
00195                                         j = a->head;
00196                                         if (!j->is_marked)
00197                                         {
00198                                                 if (j->parent == a->sister) set_orphan_rear(j);
00199                                                 if (j->parent && j->is_sink && a->r_cap > 0) set_active(j);
00200                                         }
00201                                 }
00202                                 add_to_changed_list(i);
00203                         }
00204                 }
00205                 else
00206                 {
00207                         if (!i->parent || !i->is_sink)
00208                         {
00209                                 i->is_sink = 1;
00210                                 for (a=i->first; a; a=a->next)
00211                                 {
00212                                         j = a->head;
00213                                         if (!j->is_marked)
00214                                         {
00215                                                 if (j->parent == a->sister) set_orphan_rear(j);
00216                                                 if (j->parent && !j->is_sink && a->sister->r_cap > 0) set_active(j);
00217                                         }
00218                                 }
00219                                 add_to_changed_list(i);
00220                         }
00221                 }
00222                 i->parent = TERMINAL;
00223                 i -> TS = TIME;
00224                 i -> DIST = 1;
00225         }
00226 
00227         //test_consistency();
00228 
00229         /* adoption */
00230         while ((np=orphan_first))
00231         {
00232                 orphan_first = np -> next;
00233                 i = np -> ptr;
00234                 nodeptr_block -> Delete(np);
00235                 if (!orphan_first) orphan_last = NULL;
00236                 if (i->is_sink) process_sink_orphan(i);
00237                 else            process_source_orphan(i);
00238         }
00239         /* adoption end */
00240 
00241         //test_consistency();
00242 }

template<typename captype, typename tcaptype, typename flowtype>
Graph< captype, tcaptype, flowtype >::node * Graph< captype, tcaptype, flowtype >::next_active (  )  [inline, private]

Definition at line 53 of file maxflow.cpp.

00054 {
00055         node *i;
00056 
00057         while ( 1 )
00058         {
00059                 if (!(i=queue_first[0]))
00060                 {
00061                         queue_first[0] = i = queue_first[1];
00062                         queue_last[0]  = queue_last[1];
00063                         queue_first[1] = NULL;
00064                         queue_last[1]  = NULL;
00065                         if (!i) return NULL;
00066                 }
00067 
00068                 /* remove it from the active list */
00069                 if (i->next == i) queue_first[0] = queue_last[0] = NULL;
00070                 else              queue_first[0] = i -> next;
00071                 i -> next = NULL;
00072 
00073                 /* a node in the list is active iff it has a parent */
00074                 if (i->parent) return i;
00075         }
00076 }

template<typename captype, typename tcaptype, typename flowtype>
void Graph< captype, tcaptype, flowtype >::process_sink_orphan ( node i  )  [private]

Definition at line 401 of file maxflow.cpp.

00402 {
00403         node *j;
00404         arc *a0, *a0_min = NULL, *a;
00405         int d, d_min = INFINITE_D;
00406 
00407         /* trying to find a new parent */
00408         for (a0=i->first; a0; a0=a0->next)
00409         if (a0->r_cap)
00410         {
00411                 j = a0 -> head;
00412                 if (j->is_sink && (a=j->parent))
00413                 {
00414                         /* checking the origin of j */
00415                         d = 0;
00416                         while ( 1 )
00417                         {
00418                                 if (j->TS == TIME)
00419                                 {
00420                                         d += j -> DIST;
00421                                         break;
00422                                 }
00423                                 a = j -> parent;
00424                                 d ++;
00425                                 if (a==TERMINAL)
00426                                 {
00427                                         j -> TS = TIME;
00428                                         j -> DIST = 1;
00429                                         break;
00430                                 }
00431                                 if (a==ORPHAN) { d = INFINITE_D; break; }
00432                                 j = a -> head;
00433                         }
00434                         if (d<INFINITE_D) /* j originates from the sink - done */
00435                         {
00436                                 if (d<d_min)
00437                                 {
00438                                         a0_min = a0;
00439                                         d_min = d;
00440                                 }
00441                                 /* set marks along the path */
00442                                 for (j=a0->head; j->TS!=TIME; j=j->parent->head)
00443                                 {
00444                                         j -> TS = TIME;
00445                                         j -> DIST = d --;
00446                                 }
00447                         }
00448                 }
00449         }
00450 
00451         if (i->parent = a0_min)
00452         {
00453                 i -> TS = TIME;
00454                 i -> DIST = d_min + 1;
00455         }
00456         else
00457         {
00458                 /* no parent is found */
00459                 add_to_changed_list(i);
00460 
00461                 /* process neighbors */
00462                 for (a0=i->first; a0; a0=a0->next)
00463                 {
00464                         j = a0 -> head;
00465                         if (j->is_sink && (a=j->parent))
00466                         {
00467                                 if (a0->r_cap) set_active(j);
00468                                 if (a!=TERMINAL && a!=ORPHAN && a->head==i)
00469                                 {
00470                                         set_orphan_rear(j); // add j to the end of the adoption list
00471                                 }
00472                         }
00473                 }
00474         }
00475 }

template<typename captype, typename tcaptype, typename flowtype>
void Graph< captype, tcaptype, flowtype >::process_source_orphan ( node i  )  [private]

Definition at line 324 of file maxflow.cpp.

00325 {
00326         node *j;
00327         arc *a0, *a0_min = NULL, *a;
00328         int d, d_min = INFINITE_D;
00329 
00330         /* trying to find a new parent */
00331         for (a0=i->first; a0; a0=a0->next)
00332         if (a0->sister->r_cap)
00333         {
00334                 j = a0 -> head;
00335                 if (!j->is_sink && (a=j->parent))
00336                 {
00337                         /* checking the origin of j */
00338                         d = 0;
00339                         while ( 1 )
00340                         {
00341                                 if (j->TS == TIME)
00342                                 {
00343                                         d += j -> DIST;
00344                                         break;
00345                                 }
00346                                 a = j -> parent;
00347                                 d ++;
00348                                 if (a==TERMINAL)
00349                                 {
00350                                         j -> TS = TIME;
00351                                         j -> DIST = 1;
00352                                         break;
00353                                 }
00354                                 if (a==ORPHAN) { d = INFINITE_D; break; }
00355                                 j = a -> head;
00356                         }
00357                         if (d<INFINITE_D) /* j originates from the source - done */
00358                         {
00359                                 if (d<d_min)
00360                                 {
00361                                         a0_min = a0;
00362                                         d_min = d;
00363                                 }
00364                                 /* set marks along the path */
00365                                 for (j=a0->head; j->TS!=TIME; j=j->parent->head)
00366                                 {
00367                                         j -> TS = TIME;
00368                                         j -> DIST = d --;
00369                                 }
00370                         }
00371                 }
00372         }
00373 
00374         if (i->parent = a0_min)
00375         {
00376                 i -> TS = TIME;
00377                 i -> DIST = d_min + 1;
00378         }
00379         else
00380         {
00381                 /* no parent is found */
00382                 add_to_changed_list(i);
00383 
00384                 /* process neighbors */
00385                 for (a0=i->first; a0; a0=a0->next)
00386                 {
00387                         j = a0 -> head;
00388                         if (!j->is_sink && (a=j->parent))
00389                         {
00390                                 if (a0->sister->r_cap) set_active(j);
00391                                 if (a!=TERMINAL && a!=ORPHAN && a->head==i)
00392                                 {
00393                                         set_orphan_rear(j); // add j to the end of the adoption list
00394                                 }
00395                         }
00396                 }
00397         }
00398 }

template<typename captype, typename tcaptype, typename flowtype>
void Graph< captype, tcaptype, flowtype >::reallocate_arcs (  )  [private]

num is the number of new nodes

Definition at line 87 of file graph.cpp.

00088 {
00089         int arc_num_max = (int)(arc_max - arcs);
00090         int arc_num = (int)(arc_last - arcs);
00091         arc* arcs_old = arcs;
00092 
00093         arc_num_max += arc_num_max / 2; if (arc_num_max & 1) arc_num_max ++;
00094         arcs = (arc*) realloc(arcs_old, arc_num_max*sizeof(arc));
00095         if (!arcs) { if (error_function) (*error_function)("Not enough memory!"); exit(1); }
00096 
00097         arc_last = arcs + arc_num;
00098         arc_max = arcs + arc_num_max;
00099 
00100         if (arcs != arcs_old)
00101         {
00102                 node* i;
00103                 arc* a;
00104                 for (i=nodes; i<node_last; i++)
00105                 {
00106                         if (i->first) i->first = (arc*) ((char*)i->first + (((char*) arcs) - ((char*) arcs_old)));
00107                 }
00108                 for (a=arcs; a<arc_last; a++)
00109                 {
00110                         if (a->next) a->next = (arc*) ((char*)a->next + (((char*) arcs) - ((char*) arcs_old)));
00111                         a->sister = (arc*) ((char*)a->sister + (((char*) arcs) - ((char*) arcs_old)));
00112                 }
00113         }
00114 }

template<typename captype, typename tcaptype, typename flowtype>
void Graph< captype, tcaptype, flowtype >::reallocate_nodes ( int  num  )  [private]

monotonically increasing global counter

Definition at line 63 of file graph.cpp.

00064 {
00065         int node_num_max = (int)(node_max - nodes);
00066         node* nodes_old = nodes;
00067 
00068         node_num_max += node_num_max / 2;
00069         if (node_num_max < node_num + num) node_num_max = node_num + num;
00070         nodes = (node*) realloc(nodes_old, node_num_max*sizeof(node));
00071         if (!nodes) { if (error_function) (*error_function)("Not enough memory!"); exit(1); }
00072 
00073         node_last = nodes + node_num;
00074         node_max = nodes + node_num_max;
00075 
00076         if (nodes != nodes_old)
00077         {
00078                 arc* a;
00079                 for (a=arcs; a<arc_last; a++)
00080                 {
00081                         a->head = (node*) ((char*)a->head + (((char*) nodes) - ((char*) nodes_old)));
00082                 }
00083         }
00084 }

template<typename captype, typename tcaptype, typename flowtype>
void Graph< captype, tcaptype, flowtype >::remove_from_changed_list ( node_id  i  )  [inline]

If changed_list is not NULL while calling maxflow(), then the algorithm keeps a list of nodes which could potentially have changed their segmentation label. Nodes which are not in the list are guaranteed to keep their old segmentation label (SOURCE or SINK). Example usage:

typedef Graph<int,int,int> G; G* g = new Graph(nodeNum, edgeNum); Block<G::node_id>* changed_list = new Block<G::node_id>(128);

... //! add nodes and edges

g->maxflow(); //! first call should be without arguments for (int iter=0; iter<10; iter++) { ... //! change graph, call mark_node() accordingly

g->maxflow(true, changed_list); G::node_id* ptr; for (ptr=changed_list->ScanFirst(); ptr; ptr=changed_list->ScanNext()) { G::node_id i = *ptr; assert(i>=0 && i<nodeNum); g->remove_from_changed_list(i); ! do something with node i... if (g->what_segment(i) == G::SOURCE) { ... } } changed_list->Reset(); } delete changed_list;

NOTE:

Definition at line 245 of file graph.h.

00246         { 
00247                 assert(i>=0 && i<node_num && nodes[i].is_in_changed_list); 
00248                 nodes[i].is_in_changed_list = 0;
00249         }

template<typename captype, typename tcaptype, typename flowtype>
void Graph< captype, tcaptype, flowtype >::reset (  ) 

Removes all nodes and edges. After that functions add_node() and add_edge() must be called again.

Advantage compared to deleting Graph and allocating it again: no calls to delete/new (which could be quite slow).

If the graph structure stays the same, then an alternative is to go through all nodes/edges and set new residual capacities (see functions below).

Definition at line 46 of file graph.cpp.

00047 {
00048         node_last = nodes;
00049         arc_last = arcs;
00050         node_num = 0;
00051 
00052         if (nodeptr_block) 
00053         { 
00054                 delete nodeptr_block; 
00055                 nodeptr_block = NULL; 
00056         }
00057 
00058         maxflow_iteration = 0;
00059         flow = 0;
00060 }

template<typename captype, typename tcaptype, typename flowtype>
void Graph< captype, tcaptype, flowtype >::restore_arc ( arc dest,
const arc s 
) [inline]

Definition at line 397 of file graph.h.

00397                                                    {
00398                 dest->r_cap = s.r_cap;
00399         };

template<typename captype, typename tcaptype, typename flowtype>
void Graph< captype, tcaptype, flowtype >::restore_node ( node dest,
const node s 
) [inline]

Definition at line 401 of file graph.h.

00401                                                       {
00402                 dest->next = s.next;
00403                 dest->parent = s.parent;
00404                 dest->tr_cap = s.tr_cap;
00405                 //
00406                 dest->DIST = s.DIST;
00407                 //dest->is_marked = s.is_marked;
00408                 dest->is_sink = s.is_sink;
00409                 dest->TS = s.TS;
00410         };

template<typename captype, typename tcaptype, typename flowtype>
void Graph< captype, tcaptype, flowtype >::restore_saved (  )  [inline]

Definition at line 412 of file graph.h.

00412                             {
00413                 for(int i=0;i<save.nodes.size();++i){
00414                         restore_node(save.nodes[i].dest,save.nodes[i].saved);
00415                 };
00416                 for(int i=0;i<save.arcs.size();++i){
00417                         restore_arc(save.arcs[i].dest,save.arcs[i].saved);
00418                 };
00419                 flow = save.flow;
00420                 maxflow_iteration = save.maxflow_iteration;
00421                 for(int i=0;i<2;++i){
00422                         queue_first[i] = save.queue_first[i];
00423                         queue_last[i] = save.queue_last[i];
00424                 };
00425                 TIME = save.TIME;
00426         };

template<typename captype, typename tcaptype, typename flowtype>
void Graph< captype, tcaptype, flowtype >::save ( arc x  )  [inline]

Definition at line 454 of file graph.h.

00454                           {
00455                 save(&x);
00456         };

template<typename captype, typename tcaptype, typename flowtype>
void Graph< captype, tcaptype, flowtype >::save ( arc x  )  [inline]

Definition at line 447 of file graph.h.

00447                           {
00448                 if(save.started && !x->is_saved){
00449                         save_arc(x);
00450                         x->is_saved = true;
00451                 };
00452         };

template<typename captype, typename tcaptype, typename flowtype>
void Graph< captype, tcaptype, flowtype >::save ( node x  )  [inline]

Definition at line 443 of file graph.h.

00443                            {
00444                 save(&x);
00445         };

template<typename captype, typename tcaptype, typename flowtype>
void Graph< captype, tcaptype, flowtype >::save ( node x  )  [inline]

Definition at line 436 of file graph.h.

00436                            {
00437                 if(save.started && !x->is_saved){
00438                         save_node(x);
00439                         x->is_saved = true;
00440                 };
00441         };

template<typename captype, typename tcaptype, typename flowtype>
void Graph< captype, tcaptype, flowtype >::save_arc ( arc x  )  [inline]

Definition at line 432 of file graph.h.

00432                               {
00433                 save.arcs.push_back(graph_save::arc_saved(x));
00434         };

template<typename captype, typename tcaptype, typename flowtype>
void Graph< captype, tcaptype, flowtype >::save_node ( node x  )  [inline]

Definition at line 428 of file graph.h.

00428                                 {
00429                 save.nodes.push_back(graph_save::node_saved(x));
00430         };

template<typename captype, typename tcaptype, typename flowtype>
void Graph< captype, tcaptype, flowtype >::set_active ( node i  )  [inline, private]

functions for processing active list

Definition at line 35 of file maxflow.cpp.

00036 {
00037         if (!i->next)
00038         {
00039                 /* it's not in the list yet */
00040                 if (queue_last[1]) queue_last[1] -> next = i;
00041                 else               queue_first[1]        = i;
00042                 queue_last[1] = i;
00043                 i -> next = i;
00044         }
00045 }

template<typename captype, typename tcaptype, typename flowtype>
void Graph< captype, tcaptype, flowtype >::set_orphan_front ( node i  )  [inline, private]

functions for processing orphans list

Definition at line 81 of file maxflow.cpp.

00082 {
00083         nodeptr *np;
00084         i -> parent = ORPHAN;
00085         np = nodeptr_block -> New();
00086         np -> ptr = i;
00087         np -> next = orphan_first;
00088         orphan_first = np;
00089 }

template<typename captype, typename tcaptype, typename flowtype>
void Graph< captype, tcaptype, flowtype >::set_orphan_rear ( node i  )  [inline, private]

add to the beginning of the list

Definition at line 92 of file maxflow.cpp.

00093 {
00094         nodeptr *np;
00095         i -> parent = ORPHAN;
00096         np = nodeptr_block -> New();
00097         np -> ptr = i;
00098         if (orphan_last) orphan_last -> next = np;
00099         else             orphan_first        = np;
00100         orphan_last = np;
00101         np -> next = NULL;
00102 }

template<typename captype, typename tcaptype, typename flowtype>
void Graph< captype, tcaptype, flowtype >::set_rcap ( arc a,
captype  rcap 
) [inline]

Definition at line 588 of file graph.h.

00589 {
00590         assert(a >= arcs && a < arc_last);
00591         a->r_cap = rcap;
00592 }

template<typename captype, typename tcaptype, typename flowtype>
void Graph< captype, tcaptype, flowtype >::set_trcap ( node_id  i,
tcaptype  trcap 
) [inline]

4. Functions for setting residual capacities. // NOTE: If these functions are used, the value of the flow // returned by maxflow() will not be valid! //

Definition at line 580 of file graph.h.

00581 {
00582         assert(i>=0 && i<node_num);
00583         save(nodes[i]);
00584         nodes[i].tr_cap = trcap;
00585 }

template<typename captype, typename tcaptype, typename flowtype>
void Graph< captype, tcaptype, flowtype >::start_save (  )  [inline]

Definition at line 375 of file graph.h.

00375                          {
00376                 for(int i=0;i<save.nodes.size();++i){
00377                         save.nodes[i].dest->is_saved = false;
00378                 };
00379                 for(int i=0;i<save.arcs.size();++i){
00380                         save.arcs[i].dest->is_saved = false;
00381                 };
00382                 save.nodes.clear();
00383                 save.arcs.clear();
00384                 save.flow = flow;
00385                 save.maxflow_iteration = maxflow_iteration;
00386                 for(int i=0;i<2;++i){
00387                         save.queue_first[i] = queue_first[i];
00388                         save.queue_last[i] = queue_last[i];
00389                 };
00390                 save.TIME = TIME;
00391                 save.started = true;
00392         };

template<typename captype, typename tcaptype, typename flowtype>
void Graph< captype, tcaptype, flowtype >::stop_save (  )  [inline]

Definition at line 393 of file graph.h.

00393                         {
00394                 save.started = false;
00395         };

template<typename captype, typename tcaptype, typename flowtype>
void Graph< captype, tcaptype, flowtype >::test_consistency ( node current_node = NULL  )  [private]

Definition at line 618 of file maxflow.cpp.

00619 {
00620         node *i;
00621         arc *a;
00622         int r;
00623         int num1 = 0, num2 = 0;
00624 
00625         // test whether all nodes i with i->next!=NULL are indeed in the queue
00626         for (i=nodes; i<node_last; i++)
00627         {
00628                 if (i->next || i==current_node) num1 ++;
00629         }
00630         for (r=0; r<3; r++)
00631         {
00632                 i = (r == 2) ? current_node : queue_first[r];
00633                 if (i)
00634                 for ( ; ; i=i->next)
00635                 {
00636                         num2 ++;
00637                         if (i->next == i)
00638                         {
00639                                 if (r<2){ assert(i == queue_last[r]);
00640                                 }else     assert(i == current_node);
00641                                 break;
00642                         }
00643                 }
00644         }
00645         assert(num1 == num2);
00646 
00647         for (i=nodes; i<node_last; i++)
00648         {
00649                 // test whether all edges in seach trees are non-saturated
00650                 if (i->parent == NULL) {}
00651                 else if (i->parent == ORPHAN) {}
00652                 else if (i->parent == TERMINAL)
00653                 {
00654                         if (!i->is_sink){ assert(i->tr_cap > 0);
00655                         }else             assert(i->tr_cap < 0);
00656                 }
00657                 else
00658                 {
00659                         if (!i->is_sink){ assert (i->parent->sister->r_cap > 0);
00660                         }else             assert (i->parent->r_cap > 0);
00661                 }
00662                 // test whether passive nodes in search trees have neighbors in
00663                 // a different tree through non-saturated edges
00664                 if (i->parent && !i->next)
00665                 {
00666                         if (!i->is_sink)
00667                         {
00668                                 assert(i->tr_cap >= 0);
00669                                 for (a=i->first; a; a=a->next)
00670                                 {
00671                                         if (a->r_cap > 0) assert(a->head->parent && !a->head->is_sink);
00672                                 }
00673                         }
00674                         else
00675                         {
00676                                 assert(i->tr_cap <= 0);
00677                                 for (a=i->first; a; a=a->next)
00678                                 {
00679                                         if (a->sister->r_cap > 0) assert(a->head->parent && a->head->is_sink);
00680                                 }
00681                         }
00682                 }
00683                 // test marking invariants
00684                 if (i->parent && i->parent!=ORPHAN && i->parent!=TERMINAL)
00685                 {
00686                         assert(i->TS <= i->parent->head->TS);
00687                         if (i->TS == i->parent->head->TS) assert(i->DIST > i->parent->head->DIST);
00688                 }
00689         }
00690 }

template<typename captype, typename tcaptype, typename flowtype>
Graph< captype, tcaptype, flowtype >::termtype Graph< captype, tcaptype, flowtype >::what_segment ( node_id  i,
termtype  default_segm = SOURCE 
) [inline]

After the maxflow is computed, this function returns to which segment the node 'i' belongs (Graph<captype,tcaptype,flowtype>::SOURCE or Graph<captype,tcaptype,flowtype>::SINK).

Occasionally there may be several minimum cuts. If a node can be assigned to both the source and the sink, then default_segm is returned.

Definition at line 596 of file graph.h.

00597 {
00598         if (nodes[i].parent)
00599         {
00600                 return (nodes[i].is_sink) ? SINK : SOURCE;
00601         }
00602         else
00603         {
00604                 return default_segm;
00605         }
00606 }


Member Data Documentation

template<typename captype, typename tcaptype, typename flowtype>
arc * Graph< captype, tcaptype, flowtype >::arc_last [private]

Definition at line 304 of file graph.h.

template<typename captype, typename tcaptype, typename flowtype>
arc * Graph< captype, tcaptype, flowtype >::arc_max [private]

arc_last = arcs+2*edge_num, arc_max = arcs+2*edge_num_max;

Definition at line 304 of file graph.h.

template<typename captype, typename tcaptype, typename flowtype>
arc* Graph< captype, tcaptype, flowtype >::arcs [private]

Definition at line 304 of file graph.h.

template<typename captype, typename tcaptype, typename flowtype>
Block<node_id>* Graph< captype, tcaptype, flowtype >::changed_list [private]

counter

Definition at line 318 of file graph.h.

template<typename captype, typename tcaptype, typename flowtype>
void(* Graph< captype, tcaptype, flowtype >::error_function)(char *) [private]

template<typename captype, typename tcaptype, typename flowtype>
flowtype Graph< captype, tcaptype, flowtype >::flow [private]

with a corresponding error message (or exit(1) is called if it's NULL)

Definition at line 314 of file graph.h.

template<typename captype, typename tcaptype, typename flowtype>
int Graph< captype, tcaptype, flowtype >::maxflow_iteration [private]

reusing trees & list of changed pixels

Definition at line 317 of file graph.h.

template<typename captype, typename tcaptype, typename flowtype>
node * Graph< captype, tcaptype, flowtype >::node_last [private]

Definition at line 303 of file graph.h.

template<typename captype, typename tcaptype, typename flowtype>
node * Graph< captype, tcaptype, flowtype >::node_max [private]

node_last = nodes+node_num, node_max = nodes+node_num_max;

Definition at line 303 of file graph.h.

template<typename captype, typename tcaptype, typename flowtype>
int Graph< captype, tcaptype, flowtype >::node_num [private]

Definition at line 306 of file graph.h.

template<typename captype, typename tcaptype, typename flowtype>
DBlock<nodeptr>* Graph< captype, tcaptype, flowtype >::nodeptr_block [private]

Definition at line 308 of file graph.h.

template<typename captype, typename tcaptype, typename flowtype>
const int Graph< captype, tcaptype, flowtype >::NODEPTR_BLOCK_SIZE = 128 [static, private]

Definition at line 301 of file graph.h.

template<typename captype, typename tcaptype, typename flowtype>
node* Graph< captype, tcaptype, flowtype >::nodes [private]

Definition at line 303 of file graph.h.

template<typename captype, typename tcaptype, typename flowtype>
nodeptr* Graph< captype, tcaptype, flowtype >::orphan_first [private]

list of active nodes

Definition at line 323 of file graph.h.

template<typename captype, typename tcaptype, typename flowtype>
nodeptr * Graph< captype, tcaptype, flowtype >::orphan_last [private]

Definition at line 323 of file graph.h.

template<typename captype, typename tcaptype, typename flowtype>
node* Graph< captype, tcaptype, flowtype >::queue_first[2] [private]

Definition at line 322 of file graph.h.

template<typename captype, typename tcaptype, typename flowtype>
node * Graph< captype, tcaptype, flowtype >::queue_last[2] [private]

Definition at line 322 of file graph.h.

template<typename captype, typename tcaptype, typename flowtype>
graph_save Graph< captype, tcaptype, flowtype >::save

Definition at line 374 of file graph.h.

template<typename captype, typename tcaptype, typename flowtype>
int Graph< captype, tcaptype, flowtype >::TIME [private]

list of pointers to orphans

Definition at line 324 of file graph.h.


The documentation for this class was generated from the following files:
Generated on Sun Oct 26 18:22:21 2008 for maxflow-v3.0 by  doxygen 1.4.7